// Huffman.cpp: implementation of the Huffman class.
// Written By Hatem Mostafa, 4 Jan 2005 (from CodeProject: http://www.codeproject.com/KB/recipes/Huffman_coding.aspx)
// Modified as C By klauski, 19, Nov, 2011
//////////////////////////////////////////////////////////////////////
#include <string.h>
#include <stdlib.h>
#include <malloc.h>

#include "mwave.h"

#include "Huffman.h"
#include "Huffman_private.h"


#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#endif

////////////////////////////////////////////////////////////////////

void *global_huffman_tree = 0x00000000;

int __cdecl frequencyCompare(const void *elem1, const void *elem2 )
{
	CHuffmanNode *pNodes[2] = {	(CHuffmanNode*)elem1, (CHuffmanNode*)elem2 };
	if(pNodes[0]->nFrequency == pNodes[1]->nFrequency)
		return 0;
	return pNodes[0]->nFrequency < pNodes[1]->nFrequency ? 1 : -1;
}

int __cdecl asciiCompare(const void *elem1, const void *elem2 )
{
	return ((CHuffmanNode*)elem1)->byAscii > ((CHuffmanNode*)elem2)->byAscii ? 1 : -1;
}

int __cdecl asciiCompareForPointerArray(const void *elem1, const void *elem2)
{
	return (*(CHuffmanNode**)elem1)->byAscii > (*(CHuffmanNode**)elem2)->byAscii ? 1 : -1;
}

CHuffmanNode* PopNode(CHuffmanNode *pNodes[], int nIndex, BOOL bRight)
{
	CHuffmanNode* pNode = pNodes[nIndex];
	pNode->dwCode = bRight;
	pNode->nCodeLength = 1;
	return pNode;
}

void SetHuffmanTree(HuffmanTree tree)
{
	global_huffman_tree = &tree;
}

HuffmanTree GetHuffmanTree(void)
{
	return *(HuffmanTree*)global_huffman_tree;
}

BOOL DecompressHuffman(UBYTE *pSrc, int nSrcLen, UBYTE **pDes, int *nDesLen)
{
	HuffmanTree *pTree = (HuffmanTree*)global_huffman_tree;
	HuffmanNode *pRoot, *pNode;
	DWORD nCode;
	int nDesIndex = 0;
	long nSrcIndex = 0;

	/*CHuffmanNode nodes[511], *pNode;
	CHuffmanNode *pRoot;
	HuffmanNode nodes[511], *pNode;
	
	*nDesLen = *(DWORD*)pSrc;
	*pDes = (UBYTE*)malloc(*nDesLen+1);
	nNodeCount = *(pSrc+sizeof(DWORD)) + 1;
	// initialize Huffman nodes with frequency and ascii
	for(nCount = 0; nCount < 256; nCount++)
	{
		nodes[nCount].byAscii = nCount;
	}
	for(nCount = 0; nCount < 511; nCount++)
	{
		nodes[nCount].nFrequency = 0;
		nodes[nCount].pLeft = 0;
		nodes[nCount].pRight = 0;
		nodes[nCount].pParent = 0;
	}

	nNodeSize = sizeof(int)+sizeof(UBYTE);
	nSrcIndex = nNodeSize;
	for(nCount = 0; nCount < nNodeCount; nCount++)
	{
		memcpy(&nodes[nCount], pSrc+nSrcIndex, nNodeSize);
		nSrcIndex += nNodeSize;
	}
	// construct Huffman tree
	ConstructHuffmanTree(nodes, FALSE);
	// get Huffman tree root*/

	// Find the root node of the huffman tree
	pRoot = pTree->nodes;
	while(AccessHuffmanNode(pRoot, pRoot->ofsParent) != pRoot)
		pRoot = AccessHuffmanNode(pRoot, pRoot->ofsParent);
	// Decompress 
	*nDesLen = *(DWORD*)pSrc; // copy destination final length	
	*pDes = (UBYTE*)malloc(*nDesLen + 1); // allocate buffer for decompressed buffer
	while(nDesIndex < *nDesLen)
	{
		nCode = (*(DWORD*)(pSrc+(nSrcIndex>>3)))>>(nSrcIndex&7);
		pNode = pRoot;
		while(AccessHuffmanNode(pNode, pNode->ofsLeft) != pNode)	// if node has pLeft then it must has pRight
		{	// node not leaf
			pNode = (nCode&1) ? AccessHuffmanNode(pNode, pNode->ofsRight) :
				AccessHuffmanNode(pNode, pNode->ofsLeft);
			nCode >>= 1;
			nSrcIndex++;
		}
		(*pDes)[nDesIndex++] = pNode->byAscii;
	}

	return TRUE;
}

BOOL DecompressDifferentialHuffman(BYTE *pSrc, int nSrcLen, BYTE **pDes, int *nDesLen)
{
	BYTE* Des;
	int i;
	if (DecompressHuffman(pSrc, nSrcLen, pDes, nDesLen) == FALSE)
		return FALSE;
	Des = *pDes;
	for(i = 1;i < *nDesLen; i++)
		Des[i] = Des[i] + Des[i-1];
	return TRUE;
}

long DecompressHuffmanPartially(unsigned char *pDes, unsigned char *pSrc, long nWrittenDecompressedBits, long nTotalCompressedBits, int nDesLimits)
{
	HuffmanTree *pTree = (HuffmanTree*)global_huffman_tree;
	HuffmanNode *pRoot, *pNode;
	int nDesBytesIdx = 0; // bytes
	long nSrcBitsIdx; // bits
	DWORD nCode;

	// Find the root node of the huffman tree
	pRoot = pTree->nodes;
	while(AccessHuffmanNode(pRoot, pRoot->ofsParent) != pRoot)
		pRoot = AccessHuffmanNode(pRoot, pRoot->ofsParent);
	// Decompress and copy bits
	nSrcBitsIdx = nWrittenDecompressedBits;
	while (((nSrcBitsIdx - nWrittenDecompressedBits) >> 3) < nDesLimits && nSrcBitsIdx < nTotalCompressedBits)
	{
		nCode = (*(DWORD*)(pSrc + (nSrcBitsIdx >> 3))) >> (nSrcBitsIdx & 7);
		pNode = pRoot;
		while(AccessHuffmanNode(pNode, pNode->ofsLeft) != pNode)
		{
			pNode = (nCode & 1) ? AccessHuffmanNode(pNode, pNode->ofsRight) :
				AccessHuffmanNode(pNode, pNode->ofsLeft);
			nCode >>= 1;
			nSrcBitsIdx ++;
		}
		pDes[nDesBytesIdx++] = pNode->byAscii;
	}

	return nSrcBitsIdx - nWrittenDecompressedBits;
}


void* GenerateHuffmanTree(UBYTE* pSrc, int nSrcLen, UBYTE *pDesPtr, int* nHuffLen)
{
	CHuffmanNode *nodes;
	int nCount, nNodeSize;

	nodes = (CHuffmanNode*)malloc(sizeof(CHuffmanNode) * 511);
	// initialize nodes ascii
	for(nCount = 0; nCount < 256; nCount++) nodes[nCount].byAscii = nCount;		
	for(nCount = 0; nCount < 511; nCount++)
	{
		nodes[nCount].nFrequency = 0;
		nodes[nCount].nCodeLength = 0;
		nodes[nCount].dwCode = 0;
		nodes[nCount].pLeft = 0;
		nodes[nCount].pRight = 0;
		nodes[nCount].pParent = 0;
	}

	// get ascii frequencies
	for(nCount = 0; nCount < nSrcLen; nCount++)
		nodes[pSrc[nCount]].nFrequency++;
	// sort ascii chars depending on frequency
	qsort(nodes, 256, sizeof(CHuffmanNode), frequencyCompare);
	// construct Huffman tree
	*nHuffLen = GetHuffmanTree(nodes, TRUE) - 1;
	qsort(nodes, 256, sizeof(CHuffmanNode), asciiCompare);
	nodes = (CHuffmanNode*)realloc(nodes, *nHuffLen);

	// move & write huffman tree
	nNodeSize = sizeof(int)+sizeof(UBYTE);
	// save source buffer length at the first DWORD
	*(DWORD*)pDesPtr = nSrcLen;
	pDesPtr += sizeof(DWORD);
	// save Huffman tree leaves count-1 (as it may be 256)
	*pDesPtr = *nHuffLen-1;
	pDesPtr += sizeof(UBYTE);
	// save Huffman tree used leaves nodes
	for(nCount = 0; nCount < *nHuffLen; nCount++)
	{	// the array sorted on frequency so used nodes come first
		memcpy(pDesPtr, &nodes[nCount], nNodeSize);
		pDesPtr += nNodeSize;
	}

	return nodes;
}